#include <iostream>
#include <vector>

// 三数取中
int medianOfThree(std::vector<int> &nums, int begin, int end)
{
    // 获取中间元素下标
    int midi = (end - begin) / 2 + begin;
#ifdef TEST
    std::cout << "三数取中--left:" << nums[begin] << "--midi:" << nums[midi] << "--right:" << nums[end] << std::endl;
#endif
    // 让中间元素在midi下标中
    if (nums[begin] > nums[midi]) // 左端<=中间
        std::swap(nums[begin], nums[midi]);
    if (nums[begin] > nums[end]) // 左端<=右端
        std::swap(nums[begin], nums[end]);
    if (nums[midi] > nums[end]) // 中间<=右端
        std::swap(nums[midi], nums[end]);

    return midi;
}

// 直接插入排序
void insertSort(std::vector<int>& nums, int begin, int end)
{
    for(int i = begin + 1; i <= end; i++)
    {
        int j = i - 1;
        int insertValue = nums[i];
        // 插入
        while(j >= 0)
        {
            // 该位置元素右移
            if(insertValue < nums[j])
                nums[j + 1] = nums[j];
            else
                break;
            j--;
        }
        // 插入
        nums[j + 1] = insertValue;
    }
}

// 单趟排序
std::pair<int, int> line_sort_three_range(std::vector<int> &nums, int begin, int end)
{
    // 三数取中获取基准值下标位置
    int keyi = medianOfThree(nums, begin, end);
    // 将基准值放到最左边
    std::swap(nums[keyi], nums[begin]);

    // 双指针
    // left维护的是基准值区间的左端点
    int left = begin, right = end, i = left + 1;
    while (i <= right)
    {
        // 将小的元素移动到left位置，left++，维持left左边为小于基准值的区间
        if (nums[i] < nums[left])
            std::swap(nums[i++], nums[left++]);
        // 将大于的元素移动到right的位置，right--，但是i，不移动，防止交换过来的元素还比基准值大
        else if (nums[i] > nums[left])
            std::swap(nums[i], nums[right--]);
        else
            i++;
    }
    return {left, right};
}

void _qsort_three_range(std::vector<int> &nums, int begin, int end)
{
    if (begin > end)
        return;

    // 如果小于10个元素的话，进行直接插入排序
    if(end - begin < 10)
    {
        insertSort(nums, begin, end);
        return;
    }

    // 单趟排序
    std::pair<int, int> &&lr = line_sort_three_range(nums, begin, end);
    // 左区间递归
    _qsort_three_range(nums, begin, lr.first - 1);
    // 右区间递归
    _qsort_three_range(nums, lr.second + 1, end);
}

// 三路划分快排
void qsort_three_range(std::vector<int> &nums)
{
    _qsort_three_range(nums, 0, nums.size() - 1);
}

int main()
{
    std::vector<int> nums = {1, 3, 5, 3, 2, 3, 3, 3, 7, 8, 6, 3, 3, 10, 5, 6, 3, 2, 3, 2, 4, 5, 6, 3, 1, 3, 5, 3, 2, 4, 4, 4, 3, 3, 3, 3, 6, 7};
    qsort_three_range(nums);

    for (auto item : nums)
    {
        std::cout << item << " ";
    }
    std::cout << std::endl;
    return 0;
}